package com.Algorithm.HUAWEI.four20220505;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/05/25/9:42
 * @Description:
 * @Target:
 */
public class 字符串通配符_DP {
    /*
    * 描述
    问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
    要求：
    实现如下2个通配符：
    *：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
    ？：匹配1个字符

    注意：匹配时不区分大小写。

    输入：
    通配符表达式；
    一组字符串。
    输出：

    返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
    数据范围：字符串长度：1≤s≤100
    进阶：时间复杂度：O(n^2)，空间复杂度：O(n)
    输入描述：
    先输入一个带有通配符的字符串，再输入一个需要匹配的字符串

    输出描述：
    返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
    *
    *
    * */


    /*
    *
    * 示例1
    输入：
    te?t*.*
    txt12.xls

    输出：
    false

    示例2
    输入：
    z
    zz

    输出：
    false

    示例3
    输入：
    pq
    pppq

    输出：
    false

    示例4
    输入：
    **Z
    0QZz

    输出：
    true

    示例5
    输入：
    ?*Bc*?
    abcd

    输出：
    true

    示例6
    输入：
    h*?*a
    h#a

    输出：
    false

    说明：
    根据题目描述可知能被*和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配#，故输出false
    示例7
    输入：
    p*p*qp**pq*p**p***ppq
    pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp

    输出：
    false
*/


    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String ss1 = in.readLine();
        String ss2 = in.readLine();

        boolean[][] dp = new boolean[ss1.length()+1][ss2.length()+1];

        dp[0][0] = true;


        for (int i = 0; i < dp.length; i++) {
            if (ss1.charAt(i) == '*'){
                dp[i+1][0] = true;
            }else {
                break;
            }
        }


        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if ((BigToSmall(ss1.charAt(i-1)) == BigToSmall(ss2.charAt(j-1)))||((ss1.charAt(i-1) == '?') && isCheck(ss2.charAt(j-1)))){
                    dp[i][j] = dp[i-1][j-1];
                }else if ((ss1.charAt(i-1) == '*') && isCheck(ss2.charAt(j-1))){
                    dp[i][j] = dp[i-1][j-1] || dp[i-1][j] || dp[i][j-1];
                }
            }
        }


        System.out.println(dp[ss1.length()][ss2.length()]);


/*
        if (flag == true){
            System.out.println("true");
        }else {
            System.out.println("false");
        }*/
//        String[] split = ss.split("\\*");



    }




    // 使用递归，如果是？那就通配一个，如果*那就0,1，多个。相同就一起走。
    // 入参，两个字符串，两个下标
    static boolean flag = false;  // 全局变量，只有同样末尾才会成功
    static void Recursion(String ss1,String ss2,int index1,int index2){
        // 结束条件

        System.out.println("ss1:"+ss1.length()+" ss2:"+ss2.length()+" index1:" + index1 + " index2:"+ index2);
        if (index1 == ss1.length() && index2 == ss2.length()){
            flag = true;
        }

        if (index1 >= ss1.length() || index2 >= ss2.length()){
            System.out.println("----");
            return;
        }


        // 正常如果是？那就通配一个，如果*那就0,1，多个。相同就一起走。

        if (BigToSmall(ss1.charAt(index1)) == BigToSmall(ss2.charAt(index2))){
                Recursion(ss1, ss2, index1+1, index2+1);
        }else if (ss1.charAt(index1) == '?'){
            if (isCheck(ss2.charAt(index2))){
                Recursion(ss1, ss2, index1+1, index2+1);
            }else {
                return;
            }
        }else if (ss1.charAt(index1) == '*'){
            if (isCheck(ss2.charAt(index2))){
                // 0个
                Recursion(ss1, ss2, index1+1, index2);
                // 1个
                Recursion(ss1, ss2, index1+1, index2+1);
                // 多个
                Recursion(ss1, ss2, index1, index2+1);
            }else {
                return;
            }
        }else {
            return;
        }



    }


    // 判断是否是字母和数字
    static boolean isCheck(char a){
        if ((a >= 'A' && a <= 'Z')
            || (a >= 'a' && a <= 'z')
            || (a >= '0' && a <= '9')
        ){
            return true;
        }else {
            return false;
        }
    }


    // 字母大小写自动转小写
    static char BigToSmall(char a){
        if (a >= 'A' && a <= 'Z'){
            return (char) (a+32);
        }else {
            return a;
        }
    }




}
